//////////////////////////////////////////////////////////////////////////
///	Copyright (Tencent) 2007 - All Rights Reserved
///	\file:	MemObjColl.cpp
///	Author:	robetma.
///	Date:	[2007/04/11]
///	Description:
///
//////////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "MObjColl.h"
#include "MObj.h"



//////////////////////////////////////////////////////////////////////////
//	CObjPtrArray

INT_PTR CMObjPtrArray::GetSize() const
{
	return m_nSize;
}

INT_PTR CMObjPtrArray::GetCount() const
{
	return m_nSize;
}

BOOL CMObjPtrArray::IsEmpty() const
{
	return m_nSize == 0;
}

INT_PTR CMObjPtrArray::GetUpperBound() const
{
	return m_nSize -1;
}

void CMObjPtrArray::RemoveAll()
{
	SetSize(0);
}

CMObj* CMObjPtrArray::GetAt(INT_PTR nIndex) const
{
	ASSERT(nIndex >= 0 && nIndex < m_nSize);

	return m_pData[nIndex];
}

void CMObjPtrArray::SetAt(INT_PTR nIndex, CMObj* newElement)
{
	ASSERT(nIndex >= 0 && nIndex < m_nSize);

	m_pData[nIndex] = newElement;
}

CMObj*& CMObjPtrArray::ElementAt(INT_PTR nIndex)
{
	ASSERT(nIndex >= 0 && nIndex < m_nSize);

	return m_pData[nIndex];
}

const CMObj** CMObjPtrArray::GetData() const
{
	return (const CMObj**)m_pData;
}

CMObj** CMObjPtrArray::GetData()
{
	return (CMObj**)m_pData;
}

INT_PTR CMObjPtrArray::Add(CMObj* newElement)
{
	INT_PTR nIndex = m_nSize;
	SetAtGrow(nIndex, newElement);

	return nIndex;
}

CMObj* CMObjPtrArray::operator[](INT_PTR nIndex) const
{
	return GetAt(nIndex);
}

CMObj*& CMObjPtrArray::operator[](INT_PTR nIndex)
{
	return ElementAt(nIndex);
}

CMObjPtrArray::CMObjPtrArray()
{
	m_pData = NULL;
	m_nSize = m_nMaxSize = m_nGrowBy = 0;
}

CMObjPtrArray::~CMObjPtrArray()
{
	ASSERT(this);

	delete[] (BYTE*)m_pData;
}

void CMObjPtrArray::SetSize(INT_PTR nNewSize, INT_PTR nGrowBy)
{
	ASSERT(this);
	ASSERT(nNewSize >= 0);

	if (nGrowBy >= 0)
	{
		m_nGrowBy = nGrowBy;  // set new size
	}

	if (nNewSize == 0)
	{
		// shrink to nothing
		delete[] (BYTE*)m_pData;
		m_pData = NULL;
		m_nSize = m_nMaxSize = 0;
	}
	else if (m_pData == NULL)
	{
		// create one with exact size
#ifdef SIZE_T_MAX
		ASSERT(nNewSize <= SIZE_T_MAX / sizeof(CMObj*));  // no overflow
#endif
		m_pData = (CMObj**) new BYTE[(size_t)nNewSize * sizeof(CMObj*)];

		memset(m_pData, 0, (size_t)nNewSize * sizeof(CMObj*));  // zero fill

		m_nSize = m_nMaxSize = nNewSize;
	}
	else if (nNewSize <= m_nMaxSize)
	{
		// it fits
		if (nNewSize > m_nSize)
		{
			// initialize the new elements
			memset(&m_pData[m_nSize], 0, (size_t)(nNewSize - m_nSize) * sizeof(CMObj*));
		}

		m_nSize = nNewSize;
	}
	else
	{
		// otherwise, grow array
		INT_PTR nGrowArrayBy = m_nGrowBy;
		if (nGrowArrayBy == 0)
		{
			// heuristically determine growth when nGrowArrayBy == 0
			//  (this avoids heap fragmentation in many situations)
			nGrowArrayBy = min(1024, max(4, m_nSize / 8));
		}
		INT_PTR nNewMax;
		if (nNewSize < m_nMaxSize + nGrowArrayBy)
		{
			nNewMax = m_nMaxSize + nGrowArrayBy;  // granularity
		}
		else
		{
			nNewMax = nNewSize;  // no slush
		}

		ASSERT(nNewMax >= m_nMaxSize);  // no wrap around


#ifdef SIZE_T_MAX
		ASSERT(nNewMax <= SIZE_T_MAX / sizeof(CMObj*)); // no overflow
#endif
		CMObj** pNewData = (CMObj**) new BYTE[(size_t)nNewMax * sizeof(CMObj*)];

		// copy new data from old
		memcpy_s(pNewData, (size_t)nNewMax * sizeof(CMObj*),
			m_pData, (size_t)m_nSize * sizeof(CMObj*));

		// construct remaining elements
		ASSERT(nNewSize > m_nSize);

		memset(&(pNewData[m_nSize]), 0, (size_t)(nNewSize - m_nSize) * sizeof(CMObj*));

		// get rid of old stuff (note: no destructor called)
		delete[] (BYTE*)m_pData;
		m_pData = pNewData;
		m_nSize = nNewSize;
		m_nMaxSize = nNewMax;
	}
}

INT_PTR CMObjPtrArray::Append(const CMObjPtrArray& src)
{
	ASSERT(this);
	ASSERT(this != &src);   // cannot append to itself

	INT_PTR nOldSize = m_nSize;
	SetSize(m_nSize + src.m_nSize);

	memcpy_s(m_pData + nOldSize, (size_t)(src.m_nSize) * sizeof(CMObj*),
		src.m_pData, (size_t)(src.m_nSize) * sizeof(CMObj*));

	return nOldSize;
}

void CMObjPtrArray::Copy(const CMObjPtrArray& src)
{
	ASSERT(this);
	ASSERT(this != &src);   // cannot append to itself

	if (this != &src)
	{
		SetSize(src.m_nSize);

		memcpy_s(m_pData, (size_t)(src.m_nSize) * sizeof(CMObj*),
			src.m_pData, (size_t)(src.m_nSize) * sizeof(CMObj*));
	}

}

void CMObjPtrArray::FreeExtra()
{
	ASSERT(this);

	if (m_nSize != m_nMaxSize)
	{
		// shrink to desired size
#ifdef SIZE_T_MAX
		ASSERT(m_nSize <= SIZE_T_MAX / sizeof(CMObj*)); // no overflow
#endif
		CMObj** pNewData = NULL;
		if (m_nSize != 0)
		{
			pNewData = (CMObj**) new BYTE[(size_t)m_nSize * sizeof(CMObj*)];

			// copy new data from old
			memcpy_s(pNewData, (size_t)m_nSize * sizeof(CMObj*),
				m_pData, (size_t)m_nSize * sizeof(CMObj*));
		}

		// get rid of old stuff (note: no destructor called)
		delete[] (BYTE*)m_pData;
		m_pData = pNewData;
		m_nMaxSize = m_nSize;
	}
}

/////////////////////////////////////////////////////////////////////////////

void CMObjPtrArray::SetAtGrow(INT_PTR nIndex, CMObj* newElement)
{
	ASSERT(this);
	ASSERT(nIndex >= 0);

	if (nIndex >= m_nSize)
	{
		SetSize(nIndex + 1);
	}
	m_pData[nIndex] = newElement;
}

void CMObjPtrArray::InsertAt(INT_PTR nIndex, CMObj* newElement, INT_PTR nCount)
{
	ASSERT(this);
	ASSERT(nIndex >= 0);    // will expand to meet need
	ASSERT(nCount > 0);     // zero or negative size not allowed

	if (nIndex >= m_nSize)
	{
		// adding after the end of the array
		SetSize(nIndex + nCount);  // grow so nIndex is valid
	}
	else
	{
		// inserting in the middle of the array
		INT_PTR nOldSize = m_nSize;
		SetSize(m_nSize + nCount);  // grow it to new size

		// shift old data up to fill gap
		memmove_s(&m_pData[nIndex+nCount], (size_t)(m_nSize - (nIndex + nCount)) * sizeof(CMObj*),
			&m_pData[nIndex], (size_t)(nOldSize - nIndex) * sizeof(CMObj*));

		// re-init slots we copied from
		memset(&m_pData[nIndex], 0, (size_t)nCount * sizeof(CMObj*));
	}

	// insert new value in the gap
	ASSERT(nIndex + nCount <= m_nSize);



	// copy elements into the empty space
	while (nCount--)
	{
		m_pData[nIndex++] = newElement;
	}

}

void CMObjPtrArray::RemoveAt(INT_PTR nIndex, INT_PTR nCount)
{
	ASSERT(this);
	ASSERT(nIndex >= 0);
	ASSERT(nCount >= 0);
	INT_PTR nUpperBound = nIndex + nCount;
	ASSERT(nUpperBound <= m_nSize && nUpperBound >= nIndex && nUpperBound >= nCount);

	// just remove a range
	INT_PTR nMoveCount = m_nSize - (nUpperBound);

	if (nMoveCount)
	{
		memmove_s(&m_pData[nIndex], (size_t)nMoveCount * sizeof(CMObj*),
			&m_pData[nUpperBound], (size_t)nMoveCount * sizeof(CMObj*));
	}

	m_nSize -= nCount;
}

void CMObjPtrArray::InsertAt(INT_PTR nStartIndex, const CMObjPtrArray* pNewArray)
{
	ASSERT(this);
	ASSERT(pNewArray != NULL);
	ASSERT( NULL != dynamic_cast<const CMObjPtrArray*>(pNewArray) );
	ASSERT(pNewArray);
	ASSERT(nStartIndex >= 0);


	if (pNewArray->GetSize() > 0)
	{
		InsertAt(nStartIndex, pNewArray->GetAt(0), pNewArray->GetSize());
		for (INT_PTR i = 0; i < pNewArray->GetSize(); i++)
		{
			SetAt(nStartIndex + i, pNewArray->GetAt(i));
		}
	}
}

//////////////////////////////////////////////////////////////////////////
//	class CObjPtrList.

INT_PTR CMObjPtrList::GetCount() const
{
	return m_nCount;
}

INT_PTR CMObjPtrList::GetSize() const
{
	return m_nCount;
}

BOOL CMObjPtrList::IsEmpty() const
{
	return m_nCount == 0;
}

CMObj*& CMObjPtrList::GetHead()
{
	ASSERT(m_pNodeHead != NULL);
	return m_pNodeHead->data;
}

const CMObj* CMObjPtrList::GetHead() const
{
	ASSERT(m_pNodeHead != NULL);
	return m_pNodeHead->data;
}

CMObj*& CMObjPtrList::GetTail()
{
	ASSERT(m_pNodeTail != NULL);
	return m_pNodeTail->data;
}

const CMObj* CMObjPtrList::GetTail() const
{
	ASSERT(m_pNodeTail != NULL);
	return m_pNodeTail->data;
}

POSITION CMObjPtrList::GetHeadPosition() const
{
	return (POSITION) m_pNodeHead;
}

POSITION CMObjPtrList::GetTailPosition() const
{
	return (POSITION) m_pNodeTail;
}

CMObj*& CMObjPtrList::GetNext(POSITION& rPosition) // return *Position++
{
	CNode* pNode = (CNode*) rPosition;
	ASSERT( NULL != pNode);

	rPosition = (POSITION) pNode->pNext;
	return pNode->data;
}

const CMObj* CMObjPtrList::GetNext(POSITION& rPosition) const // return *Position++
{
	CNode* pNode = (CNode*) rPosition;
	ASSERT(NULL != pNode);

	rPosition = (POSITION) pNode->pNext;
	return pNode->data;
}

CMObj*& CMObjPtrList::GetPrev(POSITION& rPosition) // return *Position--
{
	CNode* pNode = (CNode*) rPosition;
	ASSERT(NULL != pNode);

	rPosition = (POSITION) pNode->pPrev;
	return pNode->data;
}

const CMObj* CMObjPtrList::GetPrev(POSITION& rPosition) const // return *Position--
{
	CNode* pNode = (CNode*) rPosition;
	ASSERT(NULL != pNode);

	rPosition = (POSITION) pNode->pPrev;
	return pNode->data;
}

CMObj*& CMObjPtrList::GetAt(POSITION position)
{
	CNode* pNode = (CNode*) position;
	ASSERT(NULL != pNode);

	return pNode->data;
}

const CMObj* CMObjPtrList::GetAt(POSITION position) const
{
	CNode* pNode = (CNode*) position;
	ASSERT(NULL != pNode);

	return pNode->data;
}

void CMObjPtrList::SetAt(POSITION pos, CMObj* newElement)
{
	CNode* pNode = (CNode*) pos;
	ASSERT(NULL != pNode);

	pNode->data = newElement;
}

CMObjPtrList::CMObjPtrList(INT_PTR nBlockSize)
{
	ASSERT(nBlockSize > 0);

	m_nCount = 0;
	m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
	m_pBlocks = NULL;
	m_nBlockSize = nBlockSize;
}

void CMObjPtrList::RemoveAll()
{
	ASSERT(this);

	// destroy elements

	m_nCount = 0;
	m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
	m_pBlocks->FreeDataChain();
	m_pBlocks = NULL;
}

CMObjPtrList::~CMObjPtrList()
{
	try
	{
		RemoveAll();
	}
	catch (...)
	{}
	ASSERT(m_nCount == 0);
}

/////////////////////////////////////////////////////////////////////////////
// Node helpers
/*
* Implementation note: CNode's are stored in CPlex blocks and
*  chained together. Free blocks are maintained in a singly linked list
*  using the 'pNext' member of CNode with 'm_pNodeFree' as the head.
*  Used blocks are maintained in a doubly linked list using both 'pNext'
*  and 'pPrev' as links and 'm_pNodeHead' and 'm_pNodeTail'
*   as the head/tail.
*
* We never free a CPlex block unless the List is destroyed or RemoveAll()
*  is used - so the total number of CPlex blocks may grow large depending
*  on the maximum past size of the list.
*/

CMObjPtrList::CNode*
CMObjPtrList::NewNode(CMObjPtrList::CNode* pPrev, CMObjPtrList::CNode* pNext)
{
	if (m_pNodeFree == NULL)
	{
		// add another block
		CPlex* pNewBlock = CPlex::Create(m_pBlocks, (UINT)m_nBlockSize,
			sizeof(CNode));

		// chain them into free list
		CNode* pNode = (CNode*) pNewBlock->data();
		// free in reverse order to make it easier to debug
		pNode += m_nBlockSize - 1;
		for (INT_PTR i = m_nBlockSize - 1; i >= 0; i--, pNode--)
		{
			pNode->pNext = m_pNodeFree;
			m_pNodeFree = pNode;
		}
	}
	ASSERT(m_pNodeFree != NULL);  // we must have something

	CMObjPtrList::CNode* pNode = m_pNodeFree;
	m_pNodeFree = m_pNodeFree->pNext;
	pNode->pPrev = pPrev;
	pNode->pNext = pNext;
	m_nCount++;
	ASSERT(m_nCount > 0);  // make sure we don't overflow

	pNode->data = 0; // start with zero

	return pNode;
}

void CMObjPtrList::FreeNode(CMObjPtrList::CNode* pNode)
{
	ASSERT(NULL != pNode);

	pNode->pNext = m_pNodeFree;
	m_pNodeFree = pNode;
	m_nCount--;
	ASSERT(m_nCount >= 0);  // make sure we don't underflow

	// if no more elements, cleanup completely
	if (m_nCount == 0)
	{
		RemoveAll();
	}
}

/////////////////////////////////////////////////////////////////////////////

POSITION CMObjPtrList::AddHead(CMObj* newElement)
{
	ASSERT(this);

	CNode* pNewNode = NewNode(NULL, m_pNodeHead);
	pNewNode->data = newElement;
	if (m_pNodeHead != NULL)
	{
		m_pNodeHead->pPrev = pNewNode;
	}
	else
	{
		m_pNodeTail = pNewNode;
	}
	m_pNodeHead = pNewNode;
	return (POSITION) pNewNode;
}



POSITION CMObjPtrList::AddTail(CMObj* newElement)
{
	ASSERT(this);

	CNode* pNewNode = NewNode(m_pNodeTail, NULL);
	pNewNode->data = newElement;
	if (m_pNodeTail != NULL)
	{
		m_pNodeTail->pNext = pNewNode;
	}
	else
	{
		m_pNodeHead = pNewNode;
	}

	m_pNodeTail = pNewNode;
	return (POSITION) pNewNode;
}

void CMObjPtrList::AddHead(CMObjPtrList* pNewList)
{
	ASSERT(this);
	ASSERT(pNewList);

	// add a list of same elements to head (maintain order)
	POSITION pos = pNewList->GetTailPosition();
	while (pos != NULL)
	{
		AddHead(pNewList->GetPrev(pos));
	}
}

void CMObjPtrList::AddTail(CMObjPtrList* pNewList)
{
	ASSERT(this);
	ASSERT(pNewList);


	// add a list of same elements
	POSITION pos = pNewList->GetHeadPosition();
	while (pos != NULL)
	{
		AddTail(pNewList->GetNext(pos));
	}
}

CMObj* CMObjPtrList::RemoveHead()
{
	ASSERT(this);
	ASSERT(m_pNodeHead != NULL);  // throws if called on empty list


	CNode* pOldNode = m_pNodeHead;
	CMObj* returnValue = pOldNode->data;

	m_pNodeHead = pOldNode->pNext;
	if (m_pNodeHead != NULL)
	{
		m_pNodeHead->pPrev = NULL;
	}
	else
	{
		m_pNodeTail = NULL;
	}
	FreeNode(pOldNode);

	return returnValue;
}

CMObj* CMObjPtrList::RemoveTail()
{
	ASSERT(this);
	ASSERT(m_pNodeTail != NULL);  // don't call on empty list !!!


	CNode* pOldNode = m_pNodeTail;
	CMObj* returnValue = pOldNode->data;

	m_pNodeTail = pOldNode->pPrev;
	if (m_pNodeTail != NULL)
	{
		m_pNodeTail->pNext = NULL;
	}
	else
	{
		m_pNodeHead = NULL;
	}
	FreeNode(pOldNode);
	return returnValue;
}

POSITION CMObjPtrList::InsertBefore(POSITION position, CMObj* newElement)
{
	ASSERT(this);

	if (position == NULL)
	{
		return AddHead(newElement); // insert before nothing -> head of the list
	}

	// Insert it before position
	CNode* pOldNode = (CNode*) position;
	CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
	pNewNode->data = newElement;

	if (pOldNode->pPrev != NULL)
	{
		pOldNode->pPrev->pNext = pNewNode;
	}
	else
	{
		ASSERT(pOldNode == m_pNodeHead);
		m_pNodeHead = pNewNode;
	}
	pOldNode->pPrev = pNewNode;

	return (POSITION) pNewNode;
}



POSITION CMObjPtrList::InsertAfter(POSITION position, CMObj* newElement)
{
	ASSERT(this);

	if (position == NULL)
	{
		return AddTail(newElement); // insert after nothing -> tail of the list
	}

	// Insert it before position
	CNode* pOldNode = (CNode*) position;
	ASSERT( NULL != pOldNode);
	CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
	pNewNode->data = newElement;

	if (pOldNode->pNext != NULL)
	{
		pOldNode->pNext->pPrev = pNewNode;
	}
	else
	{
		ASSERT(pOldNode == m_pNodeTail);
		m_pNodeTail = pNewNode;
	}
	pOldNode->pNext = pNewNode;
	return (POSITION) pNewNode;
}

void CMObjPtrList::RemoveAt(POSITION position)
{
	ASSERT(this);

	CNode* pOldNode = (CNode*) position;
	ASSERT(pOldNode != NULL);

	// remove pOldNode from list
	if (pOldNode == m_pNodeHead)
	{
		m_pNodeHead = pOldNode->pNext;
	}
	else
	{
		pOldNode->pPrev->pNext = pOldNode->pNext;
	}

	if (pOldNode == m_pNodeTail)
	{
		m_pNodeTail = pOldNode->pPrev;
	}
	else
	{
		pOldNode->pNext->pPrev = pOldNode->pPrev;
	}
	FreeNode(pOldNode);
}


/////////////////////////////////////////////////////////////////////////////
// slow operations

POSITION CMObjPtrList::FindIndex(INT_PTR nIndex) const
{
	ASSERT(this);

	if (nIndex >= m_nCount || nIndex < 0)
	{
		return NULL;  // went too far
	}

	CNode* pNode = m_pNodeHead;
	while (nIndex--)
	{
		ASSERT(pNode != NULL);
		pNode = pNode->pNext;
	}
	return (POSITION) pNode;
}

POSITION CMObjPtrList::Find(CMObj* searchValue, POSITION startAfter) const
{
	ASSERT(this);

	CNode* pNode = (CNode*) startAfter;
	if (pNode == NULL)
	{
		pNode = m_pNodeHead;  // start at head
	}
	else
	{
		pNode = pNode->pNext;  // start after the one specified
	}

	for ( ; pNode != NULL; pNode = pNode->pNext )
	{
		if (pNode->data == searchValue)
		{
			return (POSITION) pNode;
		}
	}
	return NULL;
}

//////////////////////////////////////////////////////////////////////////
//	CMapWordToObjPtr
INT_PTR CMapWordToMObjPtr::GetCount() const
{
	return m_nCount;
}

INT_PTR CMapWordToMObjPtr::GetSize() const
{
	return m_nCount;
}

BOOL CMapWordToMObjPtr::IsEmpty() const
{
	return m_nCount == 0;
}

void CMapWordToMObjPtr::SetAt(WORD key, CMObj* newValue)
{
	(*this)[key] = newValue;
}

POSITION CMapWordToMObjPtr::GetStartPosition() const
{
	return (m_nCount == 0) ? NULL : BEFORE_START_POSITION;
}

UINT CMapWordToMObjPtr::GetHashTableSize() const
{
	return m_nHashTableSize;
}

CMapWordToMObjPtr::CMapWordToMObjPtr(INT_PTR nBlockSize)
{
	ASSERT(nBlockSize > 0);
	if (nBlockSize <= 0)
	{
		nBlockSize = 10;	// default size
	}

	m_pHashTable = NULL;
	m_nHashTableSize = 17;  // default size
	m_nCount = 0;
	m_pFreeList = NULL;
	m_pBlocks = NULL;
	m_nBlockSize = nBlockSize;
}

inline UINT CMapWordToMObjPtr::HashKey(WORD key) const
{
	// default identity hash - works for most primitive values
	return ((DWORD)key) >> 4;
}

void CMapWordToMObjPtr::InitHashTable(UINT nHashSize, BOOL bAllocNow)
//
// Used to force allocation of a hash table or to override the default
//   hash table size of (which is fairly small)
{
	ASSERT(this);
	ASSERT(m_nCount == 0);
	ASSERT(nHashSize > 0);
	if (nHashSize == 0)
	{
		nHashSize = 17;	// default value
	}

	if (m_pHashTable != NULL)
	{
		// free hash table
		delete[] m_pHashTable;
		m_pHashTable = NULL;
	}

	if (bAllocNow)
	{
		m_pHashTable = new CAssoc* [nHashSize];
		memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
	}
	m_nHashTableSize = nHashSize;
}

void CMapWordToMObjPtr::RemoveAll()
{
	ASSERT(this);

	if (m_pHashTable != NULL)
	{
		// free hash table
		delete[] m_pHashTable;
		m_pHashTable = NULL;
	}

	m_nCount = 0;
	m_pFreeList = NULL;
	m_pBlocks->FreeDataChain();
	m_pBlocks = NULL;
}

CMapWordToMObjPtr::~CMapWordToMObjPtr()
{
	try
	{
		RemoveAll();
	}
	catch (...)
	{}
	ASSERT(m_nCount == 0);
}

/////////////////////////////////////////////////////////////////////////////
// Assoc helpers
// same as CList implementation except we store CAssoc's not CNode's
//    and CAssoc's are singly linked all the time
CMapWordToMObjPtr::CAssoc* CMapWordToMObjPtr::NewAssoc()
{
	if (m_pFreeList == NULL)
	{
		// add another block
		CPlex* newBlock = CPlex::Create(m_pBlocks, (UINT)m_nBlockSize,
			sizeof(CMapWordToMObjPtr::CAssoc));
		// chain them into free list
		CMapWordToMObjPtr::CAssoc* pAssoc = (CMapWordToMObjPtr::CAssoc*) newBlock->data();
		// free in reverse order to make it easier to debug
		pAssoc += m_nBlockSize - 1;
		for (INT_PTR i = m_nBlockSize - 1; i >= 0; i--, pAssoc--)
		{
			pAssoc->pNext = m_pFreeList;
			m_pFreeList = pAssoc;
		}
	}
	ASSERT(m_pFreeList != NULL);  // we must have something

	CMapWordToMObjPtr::CAssoc* pAssoc = m_pFreeList;
	m_pFreeList = m_pFreeList->pNext;
	m_nCount++;
	ASSERT(m_nCount > 0);  // make sure we don't overflow

	pAssoc->key = 0;

	pAssoc->value = 0;

	return pAssoc;
}

void CMapWordToMObjPtr::FreeAssoc(CMapWordToMObjPtr::CAssoc* pAssoc)
{

	pAssoc->pNext = m_pFreeList;
	m_pFreeList = pAssoc;
	m_nCount--;
	ASSERT(m_nCount >= 0);  // make sure we don't underflow

	// if no more elements, cleanup completely
	if (m_nCount == 0)
	{
		RemoveAll();
	}
}

CMapWordToMObjPtr::CAssoc*
CMapWordToMObjPtr::GetAssocAt(WORD key, UINT& nHashBucket, UINT& nHashValue) const
// find association (or return NULL)
{
	nHashValue = HashKey(key);
	nHashBucket = nHashValue % m_nHashTableSize;

	if (m_pHashTable == NULL)
	{
		return NULL;
	}

	// see if it exists
	CAssoc* pAssoc;
	for (pAssoc = m_pHashTable[nHashBucket]; pAssoc != NULL; pAssoc = pAssoc->pNext)
	{
		if (pAssoc->key == key)
		{
			return pAssoc;
		}

	}
	return NULL;
}



/////////////////////////////////////////////////////////////////////////////

BOOL CMapWordToMObjPtr::Lookup(WORD key, CMObj*& rValue) const
{
	ASSERT(this);

	UINT nHashBucket, nHashValue;
	CAssoc* pAssoc = GetAssocAt(key, nHashBucket, nHashValue);
	if (pAssoc == NULL)
	{
		return FALSE;  // not in map
	}

	rValue = pAssoc->value;
	return TRUE;
}

CMObj*& CMapWordToMObjPtr::operator[](WORD key)
{
	ASSERT(this);

	UINT nHashBucket, nHashValue;
	CAssoc* pAssoc;
	if ((pAssoc = GetAssocAt(key, nHashBucket, nHashValue)) == NULL)
	{
		if (m_pHashTable == NULL)
		{
			InitHashTable(m_nHashTableSize);
		}

		// it doesn't exist, add a new Association
		pAssoc = NewAssoc();

		pAssoc->key = key;
		// 'pAssoc->value' is a constructed object, nothing more

		// put into hash table
		pAssoc->pNext = m_pHashTable[nHashBucket];
		m_pHashTable[nHashBucket] = pAssoc;
	}
	return pAssoc->value;  // return new reference
}


BOOL CMapWordToMObjPtr::RemoveKey(WORD key)
// remove key - return TRUE if removed
{
	ASSERT(this);

	if (m_pHashTable == NULL)
	{
		return FALSE;  // nothing in the table
	}

	CAssoc** ppAssocPrev;
	ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];

	CAssoc* pAssoc;
	for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
	{
		if (pAssoc->key == key)
		{
			// remove it
			*ppAssocPrev = pAssoc->pNext;  // remove from list
			FreeAssoc(pAssoc);
			return TRUE;
		}
		ppAssocPrev = &pAssoc->pNext;
	}
	return FALSE;  // not found
}


/////////////////////////////////////////////////////////////////////////////
// Iterating

void CMapWordToMObjPtr::GetNextAssoc(POSITION& rNextPosition,
									WORD& rKey, CMObj*& rValue) const
{
	ASSERT(this);
	ASSERT(m_pHashTable != NULL);  // never call on empty map

	CAssoc* pAssocRet = (CAssoc*)rNextPosition;
	ASSERT(pAssocRet != NULL);
	if (pAssocRet == NULL)
	{
		return;
	}

	if (pAssocRet == (CAssoc*) BEFORE_START_POSITION)
	{
		// find the first association
		for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
		{
			if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
			{
				break;
			}
		}
		ASSERT(pAssocRet != NULL);  // must find something
	}

	// find next association
	ASSERT(NULL != pAssocRet);
	CAssoc* pAssocNext;
	if ((pAssocNext = pAssocRet->pNext) == NULL)
	{
		// go to next bucket

		for (UINT nBucket = (HashKey(pAssocRet->key) % m_nHashTableSize) + 1;
			nBucket < m_nHashTableSize; nBucket++)
		{
			if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
			{
				break;
			}
		}
	}

	rNextPosition = (POSITION) pAssocNext;

	// fill in return data
	rKey = pAssocRet->key;
	rValue = pAssocRet->value;
}
